In a conventional networking system, the Open Shortest Path First (OSPF) routing algorithm is often used to calculate the shortest path between connected elements (e.g., a network, a router, etc.). OSPF is a link state routing protocol that stores information about every known link as a link state advertisement (LSA) within a link state database (LSDB). Using the well-known Dijkstra's algorithm to calculate the shortest path first (SPF), a routing table is computed that contains the shortest routes to every destination. This routing table is then used by the internet protocol (IP) to forward data between elements. Whenever new link information is received, OSPF runs SPF and updates routing table information.
A third version of OSPF, OSPFv3, is compatible with version 6 of the Internet Protocol (IPv6). A set of documents known as the Request For Comments (RFC) specifies Internet standards under which all versions of OSPF, including OSPFv3, need to comply. Specifically, RFC 2740 specifies that OSPF for IPv6 include multiple subnets per actual link in a network. Routing table computation is supposed to create a route entry for each IPv6 address (e.g., a subnet) assigned to a link. Each link includes its own cost, while each subnet prefix on the link adds an additional cost to that of the link. Thus, SPF calculation requires the calculation of each additional cost in addition to the cost of the link itself. This requires looking up each routing table entry corresponding to the subnets of the link, which is both computationally expensive and inefficient. Thus, there is a need for a system and method which reduces the time required for SPF calculation in addition to reducing the amount of memory required to support the SPF calculation.